package 二叉树高频题目_上_不含树型dp;

/**
 * @author 冷加宝
 * @version 1.0
 */
// 求完全二叉树的节点个数
// 测试链接 : https://leetcode.cn/problems/count-complete-tree-nodes/
public class Code09_CountCompleteTreeNodes {

    class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
    }

    public int countNodes(TreeNode root) {
        if(root == null){
            return 0;
        }
        return fun(root, 1, mostLeft(root, 1));
    }

    // cur : 当前来到的节点
    // level :  当前来到的节点在第几层
    // h : 整棵树的高度，不是cur这棵子树的高度
    // 求 : cur这棵子树上有多少节点
    public int fun(TreeNode cur, int level, int h){
        // 当前节点cur到达做底层，即：叶子结点
        if(level == h){
            return 1;
        }
        if(mostLeft(cur.right, level+1) == h){
            // cur右树上的最左节点，扎到了最深层
            return (1 << (h - level)) + fun(cur.right, level+1, h);
        }else {
            // cur右树上的最左节点，没扎到最深层
            return (1 << (h - level -1)) + fun(cur.left, level+1, h);
        }
    }

    // 当前节点是cur，并且它在level层
    // 返回从cur开始不停往左，能扎到几层
    public int mostLeft(TreeNode cur, int lev){
        while (cur != null){
            lev++;
            cur = cur.left;
        }
        return lev - 1;
    }
}
